操你的這禮拜忘記發鐵人，斷了……

不憋了，草稿全發了吧。

所以讓我們回到/src/runtime-core/renderer.ts，寫下最後一段邏輯吧。

目前我們renderer.ts的patchKeyedChildren應該長這樣：

const patchKeyedChildren = (oldChildren: VNode[], newChildren: VNode[], el: HTMLElement) => {
  let pointer = 0;
  let oldEnd = oldChildren.length - 1;
  let newEnd = newChildren.length - 1;
  // 從開頭找相同子節點
  while (pointer <= oldEnd && pointer <= newEnd) {
    const oldNode = oldChildren[pointer];
    const newNode = newChildren[pointer];
    if (isSameVnode(oldNode, newNode)) patch(oldNode, newNode, el);
    else break;
    pointer++;
  }
  // 從結尾找相同子節點
  while (pointer <= oldEnd && pointer <= newEnd) {
    const oldNode = oldChildren[oldEnd];
    const newNode = newChildren[newEnd];
    if (isSameVnode(oldNode, newNode)) patch(oldNode, newNode, el);
    else break;
    oldEnd--;
    newEnd--;
  }

  if (pointer > oldEnd) {
    // 新子有剩舊子沒剩，則創建剩餘新子
    while (pointer <= newEnd) {
      const nextPosition = newEnd + 1;
      const anchor = nextPosition < newChildren.length ? newChildren[nextPosition].el : null;
      patch(null, newChildren[pointer], el, anchor);
      pointer++;
    }
  } else if (pointer > newEnd) {
    // 新子沒剩舊子有剩，則刪除剩餘舊子
    while (pointer <= oldEnd) {
      unmount(oldChildren[pointer]);
      pointer++;
    }
  } else {
    // ......
  }
};

目前的代碼已完成了AB(CDEFGHI)JK←→AB(IDEGHC)JK括號外面的比對，剩下的工作只有找出不用變動的舊節點，並重新渲染缺的節點、刪除多的節點。接下來我們會在else下面的// ......接著寫下去。

首先我們遍歷新子，把他們的每一個key和index做出映射關係：

// 亂序比對
let oldStart = pointer;
let newStart = pointer;
// Map{newKey:index}
const keyToNewIndexMap: Map<string | number | symbol, number> = new Map();
for (let i = newStart; i <= newEnd; i++) keyToNewIndexMap.set(newChildren[i].key, i);

這麼做的用意在於讓接下來遍歷舊子時，可以用時間複雜度O(1)找出是否存在和新子相同key的舊子。只要把每個舊子和相同key的新子做出映射關係，這個映射關係的最長遞增子序列就是不用重新渲染的舊子，其他的舊子可以全部刪掉，新子可以全部渲染。

所以我們遍歷舊子：

const toBePatched = newEnd - newStart + 1;
// 宣告一個將新子項映射至舊子項（若舊子中無則映射為0）的陣列，用於後續排序
const newIndexToOldIndexMap = new Array(toBePatched).fill(0);

// 遍歷舊子，多的刪，缺的新增
for (let i = oldStart; i <= oldEnd; i++) {
  const oldChild = oldChildren[i];
  const newIndex = keyToNewIndexMap.get(oldChild.key);
  if (newIndex === undefined) unmount(oldChild);
  else {
    newIndexToOldIndexMap[newIndex - newStart] = i + 1;
    patch(oldChild, newChildren[newIndex], el);
  }
}

此時newIndexToOldIndexMap已是新子每一項在舊子中的索引。以上面舉過的例子(CDEFGHI)←→(IDEGHC)來說，與新子第0項I同key的舊子是第6項、與新子第1項D同key的舊子是第1項……與新子末項C同key的舊子是第0項。

由於我們需要用0代表舊子中不存在新子，如此不存在舊子和舊子第0項便會衝突，因此我們將舊子的每一項都+1。

也就是新子對舊子的映射關係是[6+1, 1+1, 2+1, 0, 3+1, 4+1, 0+1] = [7, 2, 3, 0, 4, 5, 1]。從中找出最長遞增子序列[2,3,4,5]，即是不需重新渲染的DEGH。

// 子節點排序
const increment = getLongestSubsequence(newIndexToOldIndexMap);
let j = increment.length - 1;
for (let i = toBePatched - 1; i >= 0; i--) {
  const index = newStart + i;
  const current = newChildren[index];
  const anchor = index + 1 < newChildren.length ? newChildren[index + 1].el : null;
  // 新子不存在於舊子則創建新節點
  if (newIndexToOldIndexMap[i] === 0) patch(null, current, el, anchor);
  // 新子既存則移動
  else {
    if (newIndexToOldIndexMap[i] !== increment[j]) hostInsert(current.el, el, anchor);
    else j--;
  }
}

以上便是diff算法的全部內容，同時我們也完成了數據更新時dom元素的比對及更新。

現在只要我們有虛擬dom，就能在數據更新時進行比對，並以最小量的dom操作，實現更新視圖。那麼虛擬dom又要從哪來？我們要怎麼做才能把開發者寫在template裡的東西變成虛擬dom？這就是我們接下來的課題了。

githubmain分支commit「[Day 20] runtime-core——完成渲染dom」